#include "1.h"

void InitDynamicArray(DArray *a)
{
    a->dp = NULL;
    a->len = 0;
    a->size = 0;

    a->InsertArrayTail = InsertArrayTail;
    a->RemoveByElement = RemoveByElement;
    a->FindElement = FindElement;
    a->DisplayDynamicArray = DisplayDynamicArray;
    a->Sort = Sort;
    a->ClearDArray = ClearDArray;
}

bool InsertArrayTail(DArray *a,ElementType element)
{
    if(a->dp == NULL)
    {
        a->size = (a->len+1) * 2;
        a->dp = malloc(sizeof(ElementType) * a->size);
        if(a->dp == NULL)
        {
            return false;
            InitDynamicArray(a);
        }
    }
    else if(a->len >= a->size)
    {
        int newSize = (a->len+1) * 2;
        ElementType *newDp = realloc(a->dp,sizeof(ElementType) * newSize);
        if(newDp == NULL)
        {
            return false;
        }
        
        a->size = newSize;
        a->dp = newDp; 
    }

    a->dp[a->len++] = element;
    return true;
}

bool RemoveByIndex(DArray *a,int index,void (ClearPtr)(ElementType))
{
    if(index < 0 || index >= a->len)
    {
        printf("删除的%d为非法位置!\n",index);
        return false;
    }
    if(ClearPtr != NULL)
    {
        ClearPtr(a->dp[index]);
    }
    for(int i = index; i < a->len-1; i++)
    {
        a->dp[i] = a->dp[i+1];
    }
    a->len--;
    return true;
}

bool RemoveByElement(DArray *a,ElementType element,bool (*funcPtr)(ElementType,ElementType),void (ClearPtr)(ElementType))
{
    for(int i = 0; i < a->len; i++)
    {
        if(funcPtr(element,a->dp[i]) == true)
        {
            if(RemoveByIndex(a,i,ClearPtr) == false)
                return false;
        }
        i--;
    }
    return true;
}

DArray FindElement(DArray *a,void * element,bool (*funcPtr)(ElementType,ElementType))
{
    DArray result;
    InitDynamicArray(&result);
    for(int i = 0; i < a->len; i++)
    {
        if(funcPtr(element,a->dp[i]) == true)
        InsertArraytail(&result,a->dp[i]);
    }
    return result;
}

void DisplayDynamicArray(DArray *a,void (*funcPtr)(ElementType))
{
    for(int i = 0; i < a->len; i++)
    {
        funcPtr(a->dp[i]);
    }
}

void FastSort(ElementType *s, int start, int end, bool (*funcPtr)(ElementType,ElementType))
{
    if(start >= end)
        return;
    int left = start;
    int right = end;
    ElementType temp = s[left];
    while(left < right)
    {
        while(left < right && funcPtr(s[right],temp) == true)
        {
            right--;
        }
        if(left < right)
        {
            s[left] = s[right];
            left++;
        }

        while(left < right && funcPtr(s[left],temp) == false)
        {
            left--;
        }
        if(left < right)
        {
            s[right] = s[left];
            right--;
        }
        s[left] = temp;
    }
    FastSort(s,start,right-1,funcPtr);
    FastSort(s,right+1,end,funcPtr);
}

bool Sort(DArray *a,bool (*funcPtr)(ElementType,ElementType))
{
    FastSort(&a->dp,0,a->len-1,funcPtr);
}

void ClearDArray(DArray *a, void (*funcPtr)(ElementType))
{
    if(funcPtr != NULL)
    for(int i = 0; i < a->len; i++)
    {
        funcPtr(a->dp[i]);
    }
    free(a);
    InitDynamicArray(a);
}